iT邦幫忙

2023 iThome 鐵人賽

DAY 25
0

https://ithelp.ithome.com.tw/upload/images/20231010/201493621BC4LsXySH.jpg
排序是電腦很常用到的演算法也是很經典的演算法種類,排序相關的演算法如下:

▌選擇排序法(Selection Sort)

算是比較簡單的排序演算法。會在「未排序」的數列中找到最小(或最大)的元素,並將其移到「最左邊」

「選擇排序法」會將數列拆分成兩部分:

  • 已排序:可選擇用「遞增」或「遞減」的方式來排列,就取決於你的需求了
  • 未排序:找出「最小/最大的數」,將它和最前面的數對調。這個數不會小於已排序的的任何數,而且也不會大於未排序的任何數。對調完後可以把它歸入已排序的數列中

▪ 畫成圖如下:

https://ithelp.ithome.com.tw/upload/images/20231010/20149362JlCiPojHtw.jpg
圖片來源

▪ 拆解成步驟如下:

  1. 找出「未排序」部分中的最小(或最大)元素

  2. 將此元素與「未排序」部分的第一個元素交換位置。交換完後,此元素就可以被歸納為「已排序」的部分

其實主要就是一直在重複步驟 1 ~ 2,直到「未排序」部分為空。每次循環後,「已排序」部分就會增加一個元素,「未排序」部分會相對減少一個元素,最終達到整個數列排序的目的

「選擇排序法」的「時間複雜度」是 O(n ^ 2) ,對於較大的資料量來說,效率可不是非常好。如果對 Big O Notation 不是很了解,可參考昨天寫的這篇文章開頭部分

下面附上 JS 實現「選擇排序法」的範例程式,使用到了兩層迴圈

function selsectionSort(arr) {
  for(let i = 0; i < arr.length -1; i ++) {
    let minIdx = i;
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[minIdx] > arr[j]) {
        minIdx = j;
      }
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];  // 使用解構賦值來交換
  }
  console.log(arr); // [1,7,8,10]
  return arr;
}
selsectionSort([1,10,7,8]);

▌插入排序法(Insertion Sort)

插入排序法一樣可以分為兩個部分,一個是「已排序」、「未排序」。將「未排序」數列中的「第一個」數持續插到「已排序」數列中的適當位置

▪ 畫成圖如下:

https://ithelp.ithome.com.tw/upload/images/20231010/20149362cFPj9Jw8hZ.png
圖片來源

▪ 拆解成步驟如下:

  1. 找到「未排序」數列中的「第一個」數。以上方的圖片來舉例,我們要將 [8,7,5,9,1,6,2,4,3] 做排序,第一個元素 "8" 是已排序的,所以「未排序」數列中的「第一個」數為 "7"
  2. 由小到大插到「已排序」的數列中,這時陣列的排序為 [7,8,5,9,1,6,2,4,3],其中 7, 8 代表已排序的陣列

其實,就是一直在重複步驟 1 ~ 2而已,直到「未排序」的陣列為空為止

下面附上 JS 實現「插入排序法」的範例程式,可看出也使用到了兩層迴圈
「插入排序法」的「時間複雜度」在最壞和平均的情況下是 O(n ^ 2),透過 insert sort & select sort 我們可有大概推敲到 O(n ^ 2)會有兩層迴圈的特性,執行時間會以指數成長。對於較大型的資料而言,此也不是最佳的選擇

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) { // 未排序的資料
    let currentVal = arr[i];
    let j;
    for (j = i - 1; j >= 0 && arr[j] > currentVal; j--) { // 已排序的資料
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = currentVal;
  }
  console.log(arr); // 輸出:[1, 2, 30, 40]
  return arr;
}

insertionSort([40, 30, 2, 1]); 

▌冒泡排序法(Bubble Sort)

冒泡排序法(或稱「泡沫排序法」)是比較相鄰的元素,一樣可以將數列分成「已排序」和「未排序」兩部分。從未排序的數列中找到第一個數,並開始往後兩兩比較,如果 比較小/較大 就 往前/往後 移動,直到未排序數列的第一個數為止!

泡沫/冒泡排序(Bubble Sort)之所以被稱為「泡沫/冒泡」,是因為在排序過程中,較大(或較小)的元素會像泡沫一樣「浮」到數列的一端。相鄰的元素會被反覆地比較和交,如果一個元素比它旁邊的元素大(在遞增排序中),那麼這兩個元素就會被交換,不斷反覆進行這個過程

▪ 畫成圖如下:

https://ithelp.ithome.com.tw/upload/images/20231010/201493624ZjxxKXZUu.png

▪ 拆解成步驟如下:

  1. 一開始整個數列被歸納為「未排序」
  2. 找出第一個數,以上圖為例就是 "5"
  3. 並把他跟後面相鄰的元素 1 做比較,由於 5 比 1 大,所以 5 和 1 就會交換位置,接下來再繼續跟下一個相鄰元素 "4" 做比較,直到比到有數比當前元素還要大為止
  4. 再回到步驟一,重複這個過程

範例是以「遞增」方式來排序數列,如果是「遞減」,一樣從第一個數開始比較,只是遇到比較大的數要往左邊放

附上 JS 實現冒泡排序法「遞增」排列的範例程式。「冒泡排序法」的「時間複雜度」是 O(n ^ 2),因此也不適合大型的資料

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) { 
    // 上面減去 i 是因為在外層迴圈執行完一輪後,最大的元素會被推到數列的末端,就不再需要與它進行比較了
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  console.log(arr); // [1, 2, 3, 4]
  return arr;
}

bubbleSort([4, 3, 2, 1]);

▌快速排序法(Quick Sort)

比起前面的演算法,快速排序比較難懂一點。使用了分治法 把一個複雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併,這也是它效率比較好的原因。(這邊我是截自維基百科,怎麼覺得有點繞口@@)

▪ 畫成圖如下:

https://ithelp.ithome.com.tw/upload/images/20231010/20149362yUlgv9US5K.png
圖片來源

▪ 拆解成步驟如下:

  1. 先挑選數列中的任一個元素作為基準值(Pivot),以上圖中是挑了 "8"
  2. 分割(Partitioning):重新排列數組,所有比基準值小的元素放在基準值的前面; 比基準值大的元素放在基準值的後面。這邊你可能會看到 PivotIndex,這個詞,用來表示基準值在數列中的位置
  3. 遞迴(Recursive):對基準值左側和右側的兩個子數組重複以上的步驟

附上 JS 實現「快速排序法」的範例程式
在最差和平均的情況下,「快速排序法」有不同的時間複雜度。在最差的情況中執行時間為 O(n ^ 2),就跟選擇排序法一樣;平均情況下的執行時間為 O(n log n)。會有這樣的差異來自於基準值的選擇,也就是當基準不斷的遇到最大或最小元素時,執行時間就會比較慢

function quickSort(arr) {
  if (arr.length <= 1) return arr; // 如果陣列長度 <1,就沒什麼好排列的
  
  const pivot = arr[0]; // 選擇第一個元素作為基準
  const left = []; // 存放比基準點小的元素
  const right = []; // 存放比基準點大的元素

  for (let i = 1; i < arr.length; i++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }
   
  return quickSort(left).concat(pivot, quickSort(right));  // [1, 1, 2, 3, 6, 8, 10]
}

quickSort([3, 6, 8, 10, 1, 2, 1]); 

▌總結

以上介紹的這些排序演算法在不同的情況下具有不同的效能、特性。選擇排序法、插入排序法通常不太適合用在於大型資料集上,反而快速排序法會更適合,不過選擇一個好的基準值是快速排序法的效率好壞關鍵

▌參考資料

  1. Searching & Sorting
  2. 計算機概論 全華出版 & 白話演算法 旗標出版
  3. 初學者學演算法

上一篇
Day 24 | 演算法:Big O Notation & 最大最小數找法
下一篇
Day 26 | 演算法:二元搜尋法(Binary Search)
系列文
來場計概入門課吧X資訊人該了解的通識素養31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言